﻿using System.Collections.Generic;
using System.Linq;

namespace QuickMenus
{
    /// <summary>
    /// A specialized collection meant to associate actions with a command.
    /// </summary>
    internal class MenuTrie
    {
        private TrieNode root;

        public MenuTrie()
        {
            root = new TrieNode();
        }

        /// <summary>
        /// Returns all strings that are associated with a value in this collection.
        /// </summary>
        /// <returns>A readonly collection of keys.</returns>
        public IEnumerable<string> Keys
        {
            get
            {
                return KeysBelow(string.Empty, root);
            }
        }

        /// <summary>
        /// Returns all values that stored in this collection.
        /// </summary>
        /// <returns>A readonly collection of menu items.</returns>
        public IEnumerable<MenuItem> Values
        {
            get
            {
                return (from node in AllBelow(root)
                        select node.MenuLink).Distinct();
            }
        }

        /// <summary>
        /// Fetches from this collection the menu item associated with a key.
        /// </summary>
        /// <param name="key">The key to evaluate.</param>
        /// <returns>The value associated with a key.</returns>
        public MenuItem Get(string key)
        {
            TrieNode subject;
            subject = NavigateTo(key);
            return null == subject ? null : subject.MenuLink;
        }

        /// <summary>
        /// Navigates the collection, looking for keys that meet the criteria to be a candidate for this.
        /// </summary>
        /// <param name="key">The beginning of each key to be included.</param>
        /// <returns>the subset of keys that are associated with a value, and begin in the specified manner</returns>
        public IEnumerable<string> GetCandidates(string key)
        {
            IEnumerable<string> retval;
            var subjectRoot = NavigateTo(key);
            if(null == subjectRoot)
            {
                retval = Enumerable.Empty<string>();
            }
            else
            {
                retval = KeysBelow(key, subjectRoot);
            }
            return retval;
        }
        
        /// <summary>
        /// Adds a key/value pair to be stored in the collection.
        /// </summary>
        /// <param name="key">The distinct string that should be used to identify a value.</param>
        /// <param name="entry">The value that should be stored in the collection.</param>
        public void Put(string key, MenuItem entry)
        {
            NavigateTo(key, true).MenuLink = entry;
        }

        /// <summary>
        /// Disassociate a key from a value.
        /// </summary>
        /// <param name="key">The identifier that no longer belongs in the collection.</param>
        public void Remove(string key)
        {
            var subjectNode = NavigateTo(key);

            if (null != subjectNode)
            {
                subjectNode.MenuLink = null;
                var below = AllBelow(subjectNode);
                if (!below.Any())
                {
                    var parent = NavigateTo(key.Substring(-1));
                    parent.Next.Remove(key.First());
                }
            }
        }

        //Remove all key/value pairs from the collection indiscriminately.
        public void Clear()
        {
            root = new TrieNode();
        }

        /// <summary>
        /// Traverse the Trie to find a particular node.
        /// </summary>
        /// <param name="key">The value to which should be navigated.</param>
        /// <param name="addNewNodes">Determines whether or not we should modify the trie to accomodate the navigation.</param>
        /// <returns>The node that exists at the given path.</returns>
        private TrieNode NavigateTo(string key, bool addNewNodes = false)
        {
            TrieNode cursor = root;

            while (key.Any())
            {
                var lead = key.First();
                if (!cursor.Next.ContainsKey(lead))
                {
                    if (addNewNodes)
                    {
                        cursor.Next[lead] = new TrieNode();
                    }
                    else
                    {
                        cursor = null;
                        break;
                    }
                }
                cursor = cursor.Next[lead];
                key = key.Substring(1);
            }

            return cursor;
        }

        /// <summary>
        /// Fetches all values that are stored after a certain node in a trie.
        /// </summary>
        /// <param name="node">The root of the sub trie that should be used.</param>
        /// <returns>A list of all the values beyond a certain point in a trie.</returns>
        private static IEnumerable<TrieNode> AllBelow(TrieNode node)
        {
            IEnumerable<TrieNode> retval;

            if (null == node.MenuLink)
            {
                retval = Enumerable.Empty<TrieNode>();
            }
            else
            {
                retval = new[] { node }.AsEnumerable();
            }

            foreach (char key in node.Next.Keys)
            {
                retval = retval.Union(AllBelow(node.Next[key]));
            }            

            return retval;
        }

        /// <summary>
        /// Finds all keys that are associated with values stored after a certain node in a trie.
        /// </summary>
        /// <param name="prefix">Text that should be prepended to all options. (a starting point in the sub trie)</param>
        /// <param name="node">The root of the sub trie to be evaluated.</param>
        /// <returns></returns>
        private static IEnumerable<string> KeysBelow(string prefix, TrieNode node)
        {
            IEnumerable<string> retval;

            if(null == node.MenuLink)
            {
                retval = Enumerable.Empty<string>();
            }
            else
            {
                retval = new[] { prefix }.AsEnumerable();
            }

            foreach(char key in node.Next.Keys)
            {
                retval = retval.Union(KeysBelow(prefix + key, node.Next[key]));
            }

            return retval;
        }

        /// <summary>
        /// Encapsulates interactions with a single entry in a trie.
        /// </summary>
        private class TrieNode
        {
            /// <summary>
            /// Holds all of the edges to the next set of Nodes.
            /// </summary>
            /// <returns></returns>
            public Dictionary<char, TrieNode> Next { get; set; }

            public MenuItem MenuLink { get; set; }

            public TrieNode()
            {
                MenuLink = null;
                Next = new Dictionary<char, TrieNode>();
            }
        }
    }
}
